package main.java.exercise;

import main.java.framework.StudentInformation;
import main.java.framework.StudentSolution;

import java.util.Arrays;

public class StudentSolutionImplementation implements StudentSolution {
    @Override
    public StudentInformation provideStudentInformation() {
        return new StudentInformation(
                "", // Vorname
                "", // Nachname
                "" // Matrikelnummer
        );
    }

    /**
     * computes the euclidean distance for two points in vector space R^2
     * @param a origin point
     * @param b destination point
     * @return euclidean distance between two points with double precision
     */
    private double euclideanDistance(Point a, Point b) {
        if (a == null || b == null) return Integer.MAX_VALUE;
        if (a == b) return 0d;

        return Math.sqrt(
            Math.pow(a.getX() - b.getX(), 2) +
            Math.pow(a.getY() - b.getY(), 2)
        );
    }

    /**
     * naive implementation of findClosestPair
     * @param points array of points in euclidean space
     * @param closestPair reference to a container object for two points
     */
    private void findClosestPairNaive(Point[] points, ClosestPair closestPair) {
        double min = Integer.MAX_VALUE, dist;

        for (Point a : points) {
            for (Point b : points) {
                if (a == b || b == null) continue;
                dist = euclideanDistance(a, b);
                if (dist < min) {
                    min = dist;
                    closestPair.setPoint1(a);
                    closestPair.setPoint2(b);
                }
            }
        }
    }

    /**
     * slightly optimized version of findClosestPairNaive, in which no
     * unnecessary symmetric comparisons occur
     * @param points array of points in euclidean space
     * @param closestPair reference to a container object for two points
     */
    private void findClosestPairOptimized(Point[] points, ClosestPair closestPair) {
        Point[] points_sub = new Point[points.length];
        double min = Integer.MAX_VALUE, dist;

        // initialization
        for (int i = 0; i < points.length; i++)
            points_sub[i] = points[i];

        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                // distance to itself is ignored
                // already de-queued points are ignored as well
                if (i == j || points_sub[j] == null) continue;

                // generate distance metric for euclidean space
                dist = euclideanDistance(points[i], points_sub[j]);

                // compare with previous distance metrics
                if (dist < min) {
                    min = dist;
                    closestPair.setPoint1(points[i]);
                    closestPair.setPoint2(points[j]);
                }
            }
            // prevent symmetric comparisons
            // if the outer loop has already iterated all distances for a
            // point a, there is no point in having future iterations compare
            // the euclidean distance of another point b to point a, so we
            // de-queue a
            points_sub[i] = null;
        }
    }

    /**
     * finds the maximum integer in a given array
     * naive O(n) implementation
     * @param numbers int[] of numbers
     * @return 0 for empty array, max element otherwise
     */
    public int findMax(int[] numbers) {
        if (numbers.length == 0) return 0;
        int max = numbers[0];
        for (int i = 1; i < numbers.length; i++)
            if (numbers[i] > max)
                max = numbers[i];
        return max;
    }

    /**
     * assign a closest pair by finding two points of least euclidean distance
     * both implementation of complexity class O(n^2)
     * @param points array of points in euclidean space
     * @param closestPair reference to a container object for two points
     */
    public void findClosestPair(Point[] points, ClosestPair closestPair) {
        //findClosestPairNaive(points, closestPair);
        findClosestPairOptimized(points, closestPair);
    }

    /**
     * suffers to insane overhead (due to array replication) and has simply
     * too high a complexity to be a solution to any of the given problem
     * sizes.
     * similar in spirit though to the dynamic solution, just without the
     * optimization
     */
    private boolean hasSubsetSumNaiveRecursive(int sum, int[] numbers) {
        if (sum == 0) return true;
        if (sum < 0) return false;
        if (numbers.length == 0) return false;

        int[] numbers_sub = new int[numbers.length - 1];
        int current;
        for (int i = 0; i < numbers.length; i++) {
            current = numbers[i];
            for (int j = 0; j < numbers_sub.length; j++) {
                if (i == j) continue;
                numbers_sub[j] = numbers[j >= i ? (j + 1) : j];
            }
            if (hasSubsetSum(sum - current, numbers_sub)) return true;
        }

        return false;
    }

    /**
     * forms all possible 2^n power sets in O(n*2^n) time, but with too high a
     * space complexity, requiring O(2^n) space
     */
    private boolean hasSubsetSumIterative(int sum, int[] numbers) {
        if (sum == 0) return true;
        if (sum < 0) return false;
        if (numbers.length == 0) return false;

        int n = numbers.length;
        int permutations = (int) Math.pow(2, numbers.length);

        int[] sums = new int[permutations];

        for (int i = 0; i < permutations; i++) {
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0)
                    sums[i] += numbers[j];
                if (sums[i] == sum) return true;
            }
        }

        return false;
    }

    // simple recursive implementation that includes/excludes numbers in trials

    /**
     * follows a trivially easy to understand idea, one that is generally
     * useful for explaining how power sets are formed in the first place:
     * "for each element, you take two possibilities, one in which you include
     * the possibility, one in which you don't, that gives you the power sum"
     */
    private boolean hasSubsetSumDynamic(int sum, int[] numbers, int start) {
        if (sum == 0) return true;
        if (sum < 0) return false;
        if (start >= numbers.length) return false;

        int with = sum - numbers[start++];

        boolean has_with    = hasSubsetSumDynamic(with, numbers, start);
        boolean has_without = hasSubsetSumDynamic(sum,  numbers, start);

        return has_with || has_without;
    }

    /**
     * verifies if any combination of numbers can be combined to form a sum
     * that equals the given parameter
     * @param sum sum value to be verified against
     * @param numbers numbers to make combinations of
     * @return whether a subset forms the given sum or not
     */
    public boolean hasSubsetSum(int sum, int[] numbers) {
        if (numbers.length == 0) return sum == 0;
        return hasSubsetSumDynamic(sum, numbers, 0);
    }

}
